package com.lsa.edmonds.chap8;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Stack;

public class HTower
{
    final static int size = 8;
    
    public static void main(String[] args)
    {
        List<Stack<Integer>> towers = new ArrayList<Stack<Integer>>();

        Stack<Integer> tower = new Stack<Integer>();
        
        for( int i = size; i > 0; i-- )
        {
            tower.add(i);
        }
        
        towers.add(tower);
        Stack<Integer> oldTower = tower;
        
        tower = new Stack<Integer>();
        towers.add(tower);
        
        tower = new Stack<Integer>();
        towers.add(tower);
        
        printTowers(towers, size);
        solve(oldTower.size(), towers, 0, 1, 2);
        
        // IND: t(n) = 2^n-1
        //t(n) = 2*t(n-1) + 1 = 2*(2^(n-1) - 1) + 1= 2^n - 2 + 1 = 2^n -1; 
        //QED
    }
    
    static Set states = new HashSet();
    static int no = 1; 
    public static void printTowers(List<Stack<Integer>> towers, int size)
    {
        String str = getPrintString(towers, size);
        if (!states.contains(str))
        {
            System.out.println("#" + no++);
            states.add(str);
            System.out.println(str);
        }
    }
    
    public static String getPrintString(List<Stack<Integer>> towers, int size)
    {
        StringBuffer returnSB = new StringBuffer();
        int level = 1;
        final String emptyStr = " ";
        
        while(level < size + 1)
        {
            for (int i = 0; i < towers.size(); ++i)
            {
                returnSB.append((i == 0? "|" : ""));
                
                Stack<Integer> stack = towers.get(i);
                if (level - 1 > size - stack.size() - 1)
                {
                    returnSB.append(String.format("%-"+emptyStr.length()+"d|",stack.get( stack.size() - 1 - (level - 1 - (size - stack.size())))));
                }
                else
                {
                    returnSB.append("" + emptyStr+"|");
                }
            }
            
            returnSB.append("\r\n");
            level++;
        }
        
        for (int i = 0; i < towers.size()*2 + 1; ++i)
        {
        	returnSB.append("H");
        }
        
        returnSB.append("\r\n");
        return returnSB.toString();
    }
    
    public static void solve(int n, List<Stack<Integer>> towers, int srcTower, int spareTower, int dstTower)
    {
        printTowers(towers, size);
        if (n < 1)
        {
            return;
        }
        else
        {
            solve(n - 1, towers, srcTower, dstTower, spareTower );
            towers.get(dstTower).add(towers.get(srcTower).pop());
            solve(n - 1, towers, spareTower, srcTower, dstTower );
        }
    }
}
